import { isSorted, randomArr } from "../util";

/**
 * 冒泡排序
 * @param arr 
 */
const bs = (arr: number[]) => {
    let len = arr.length;

    /**
     * 交换两个元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    /**
     * 比较两个元素的大小
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => arr[l] = arr[r]

    // 比较
    for (let i = 0; i < len; i++) {
        let sorted = true,
            end = 0;
        for (let j = 0; j < len; j++) {
            // 前面比后面大的，交换位置
            if (compare(j, j + 1) > 0) {
                // 交换
                swap(j, j + 1);

                // 标记sorted为false
                sorted = false

                // 给end赋值
                end = j;
            }
        }

        // len赋值为end (0到len的位置还没排好序, end后面的已经排好了)
        len = end;
        // i 赋值为-1
        i = -1

        // 经历过一个内循环，不交换元素，说明是已经排好序的，结束循环即可
        if (sorted) break;
    }
}

/**
 * 选择排序
 * @param arr 
 */
const ss = (arr: number[]) => {
    // 获取长度
    const len = arr.length;
    // 校验数组
    if (len < 2) return;

    /**
     * 比较两个值的大小
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => arr[l] - arr[r];

    /**
     * 移动元素
     * @param s 开始位置
     * @param e 结束位置
     */
    const move = (s: number, e: number) => {
        for (let i = e; i > s; i--) {
            arr[i] = arr[i - 1]
        }
    }

    // 从 1 开始，把0位置当作是已经排好序的
    for (let i = 1; i < len; i++) {
        // 一遍里层循环之后，i应该插入的位置
        let tag = -1;

        // 遍历i之前的元素，和i进行比较
        for (let j = i - 1; j >= 0; j--) {
            // 前面的元素更大，记录位置
            if (compare(j, i) > 0) {
                tag = j
            }
        }

        // 前面存在比i位置大的元素，才进行处理
        if (tag !== -1) {
            // 1. 保存当前的元素
            const inserted = arr[i];

            // 2. 从tag位置移动到i位置
            move(tag, i);

            // 3. 将i插入到tag位置
            arr[tag] = inserted;
        }

    }

}

/**
 * 堆排序
 * @param arr 
 */
const hs1 = (arr: number[]) => {
    let len = arr.length;
    // 数组元素小于2，不用排序
    if (len < 2) return;

    // 非叶子节点的结尾
    const e = (len >> 1) - 1;

    /**
     * 获取左孩子
     * @param i 
     */
    const getLeft = (i: number) => (i << 1) + 1;

    /**
     * 获取右孩子
     * @param i 
     */
    const getRight = (i: number) => (i << 1) + 2;

    /**
     * 获取左右孩子的最大值索引
     * @param l 
     * @param r 
     */
    const max = (l: number, r: number) => {
        const le = arr[l],
            re = arr[r];
        // 只有左孩子，没有右孩子 (交换元素下滤是，长度减一了，数组没变，可能导致r等于len是可以访问数组)     
        if (re == undefined || r >= len) return l;
        // 谁大返回谁的索引
        return le > re ? l : r
    }

    /**
     * 交换两个元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

    // 1. 原地建堆 (自底而上的下滤)
    const down = (i = 0) => {
        const sizes = len >> 1

        // sizes是非叶子节点的数量 (下滤只需要针对非叶子节点的数量)
        while (i < sizes) {
            let li = getLeft(i),
                ri = getRight(i);
            // console.log(i, li, ri)
            // 1. 获取左右孩子的最大值
            const maxI = max(li, ri);
            // 2. 比较i位置和左右孩子的最大值
            // i比左右还大, 结束循环
            if (max(maxI, i) === i) {
                break;
            }

            // i比左右孩子小, 交换位置
            // console.log(maxI, i)
            swap(maxI, i);

            // 更换i
            i = maxI;
        }
    }

    // 对非叶子节点进行下滤建堆
    for (let i = e; i >= 0; i--) {
        down(i)
    }


    // 2. 依次进行交换 (直到元素小于1为止)
    while (len > 1) {
        // 1. 第一个元素和最后一个元素交换位置 (len减1了，相当于不把最后一个元素算在内了)
        swap(0, --len)

        // 2. 对第一个元素进行下滤 (恢复堆的性质)
        down()
    }

}

/**
 * 堆排序
 * @param arr 
 */
const hs = (arr: number[]) => {
    let len = arr.length;

    // 小于两个元素不需要排序
    if (len < 2) return;

    /**
     * 获取左孩子
     * @param i 
     */
    const getLeft = (i: number) => (i << 1) + 1;

    /**
     * 获取右孩子
     * @param i 
     */
    const getRight = (i: number) => (i << 1) + 2;

    /**
     * 获取左右孩子最大的孩子索引
     * @param l 
     * @param r 
     */
    const max = (l: number, r: number) => {
        const le = arr[l];
        const re = arr[r];

        // 右节点越界了，直接返回左边孩子
        if (r >= len) return l

        // 看谁大，就返回谁的索引
        return le > re ? l : r
    }

    /**
     * 交换两个元素的位置
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    /**
     * 下滤 
     * @param i (默认是对0位置下溢) 
     */
    const down = (i = 0) => {
        const sizes = len >> 1;
        // 不断的对非叶子节点下溢
        while (i < sizes) {
            // 1. 获取左右孩子
            const li = getLeft(i),
                ri = getRight(i);

            // 2. 获取左右孩子比较大的一方
            const maxI = max(li, ri);

            // 3. 左右孩子比较大的和父亲比较大小

            // 父亲比左右孩子都大，直接结束循环
            if (max(maxI, i) === i) {
                break;
            }

            // 4. 孩子节点比较大，交换位置
            swap(maxI, i);

            // 5. 更改i
            i = maxI

        }

    }

    // 1. 原地建堆
    const sizes = (len >> 1) - 1
    for (let i = sizes; i >= 0; i--) {
        down(i)
    }


    // 2. 第一个元素不停的与最后一个元素交换位置
    while (len > 1) {
        // 交换位置
        swap(0, --len);

        // 对0位置进行调整，保持二叉大顶堆的性质
        down()
    }

}


/**
 * 快速排序
 * @param arr 
 */
const qs2 = (arr: number[]) => {
    const len = arr.length;
    // 长度小于2, 不需要进行排序
    if (len < 2) return;

    // 创建锚点 [s, e)
    const createPivot = (s = 0, e = len) => {
        if (s >= e) return
        // 1. 以arr[s]位置作为锚点
        const pivot = arr[s];

        /**
         * 元素与轴点比较大小
         * @param l 
         */
        const compare = (l: number) => arr[l] - pivot;

        /**
         * 交换元素位置
         * @param l 
         * @param r 
         */
        const replace = (l: number, r: number) => {
            arr[l] = arr[r]
        }

        // 确定start和end
        let start = s,
            end = e - 1;
        // 遍历，将小于pivot的放在左边,大于pivot放在右边
        // 默认从后往前遍历, 找到比pivot小的, 交换end和start的位置, 转向从start开始向后遍历, 找到比pivot的位置, 同理和end交换.转为从后前面遍历
        while (start < end) {
            // 后 -> 前
            while (start < end) {
                // 找到了比轴点小的元素, 交换元素, 结束该循环
                if (compare(end) < 0) {
                    // 替换
                    replace(start, end);
                    // 结束循环
                    break;
                }
                // 找不到, 往前走
                end--;
            }

            // 前 -> 后
            while (start < end) {
                // 找到了比pivot大的元素
                if (compare(start) > 0) {
                    // 替换位置
                    replace(end, start)

                    // 结束循环
                    break;
                }
                // 找不到, 继续往后找
                start++
            }

        }

        // 到这, start肯定等于end

        // start(end)的位置就是pivot要放置的位置
        arr[end] = pivot;

        // pivot左边继续构造轴点
        //! 注意是左闭右开
        createPivot(s, end)

        // pivot右边继续构造轴点
        //! 注意是左闭右开 
        createPivot(end + 1, e)

    }

    createPivot();
}


/**
 * 归并排序
 * @param arr 
 */
const ms2 = (arr: number[]) => {
    const len = arr.length;
    // 数组长度小于2, 不需要排序
    if (len < 2) return;

    /**
     * 合并
     * @param s 开始 
     * @param m 中间索引
     * @param e 右边索引
     */
    const merge = (s: number, m: number, e: number) => {
        // 1. 确定 ai(数组开始的索引), li (左边数组), le(左边数组的结尾), ri(右边数组的开始位置), re(右边数组的结束位置)
        let ai = s,
            li = 0,
            le = m - s,
            ri = m,
            re = e;

        // 2. 拷贝左边的数组
        const leftArr = arr.slice(s, m)

        /**
         * 比较大小 (注意的是要用leftArr的值比较)
         * @param l 
         * @param r 
         */
        const compare = (l: number, r: number) => leftArr[l] - arr[r];

        /**
         * l的值去替换ai的值
         * @param l 
         */
        const replace = (target: number) => arr[ai] = target;

        // 3. 开始遍历, 排序
        while (li < le && ri < re) {
            // 左边 > 右边
            if (compare(li, ri) > 0) {
                // ri去替换ai
                replace(arr[ri]);
                ri++;
            } else {
                // 左边 <= 右边
                //! 注意的是用leftArr替换 
                replace(leftArr[li]);
                li++
            }
            ai++;
        }

        // 右边的先结束 (左边的先结束不用处理)
        //! 注意的是用leftArr替换 
        if (ri >= re) {
            for (let i = li; i < le; i++) {
                arr[ai++] = leftArr[i]
            }
        }
    }

    /**
     * 拆分合并
     * @param s 
     * @param e 
     */
    const sort = (s: number, e: number) => {
        // 至少两个元素才进行拆分
        if (e - s < 2) return

        // 获取中间元素
        const m = (s + e) >> 1;

        // 拆分左边
        sort(s, m);

        // 拆分右边
        sort(m, e)

        // 合并
        return merge(s, m, e)
    }

    return sort(0, len)
}

/**
 * 计数排序
 * @param arr 
 */
const cs = (arr: number[]) => {
    const len = arr.length;
    // 1. 获取最大和最小值
    let max = arr[0],
        min = arr[0];

    for (let i = 1; i < len; i++) {
        // 比max大, 交换位置
        if (arr[i] > max) {
            max = arr[i];
        }
        // 比min小, 交换位置
        if (arr[i] < min) {
            min = arr[i]
        }
    }

    // 2. 创建max - min + 1 长度的数组
    //! 特别主要默认要填充0
    const countArr = new Array(max - min + 1).fill(0);

    // 3. 对每次出现的元素进行计数
    const cLen = countArr.length;
    for (let i = 0; i < len; i++) {
        countArr[arr[i] - min]++
    }

    // 4. 对前一次的计数进行累加 (此时某位置的次数代表自己是数组排序的第几位)
    for (let i = 1; i < cLen; i++) {
        // 累加上前一次的次数
        countArr[i] += countArr[i - 1];
    }

    // 5. 创建已经新数组，存放已经排好序的数组
    const newArr = new Array(len);
    for (let i = 0; i < len; i++) {
        // arr[i] - min 是获取i位置
        // countArr[arr[i] - min] 是获取元素arr[i] 排序的位数, -1就得到自己的位置了
        newArr[--countArr[arr[i] - min]] = arr[i]
    }

    // 6. 将已经排好序的数组转移到arr忠
    for (let i = 0; i < len; i++) {
        arr[i] = newArr[i]
    }
}

const qs = (arr: number[]) => {
    const len = arr.length;
    // 不需要排序
    if (len < 2) return;

    /**
     * 创建轴点
     * @param s 
     * @param e 
     */
    const createPivot = (s = 0, e = arr.length) => {
        // 少于两个元素的, 不需要创建轴点
        if (e - s < 2) return;

        // 保存轴点
        const pivot = arr[s];

        // 确定开始和结束位置
        let start = s,
            end = e - 1;

        /**
         * 和轴点比较大小
         * @param t 
         */
        const compare = (t: number) => arr[t] - pivot;

        /**
         * 替换位置
         * @param l 
         * @param t 
         */
        const replace = (l: number, t: number) => arr[l] = arr[t]

        while (start < end) {
            // 从右边开始
            while (start < end) {
                // 找到了比轴点小的值
                if (compare(end) < 0) {
                    // 替换start位置
                    replace(start, end)

                    // 结束该层循环
                    break;
                }
                // 找不到比pivot小的元素, 继续往前找
                end--;
            }

            // 从左边开始
            while (start < end) {
                // 找到了比轴点大的元素
                if (compare(start) > 0) {
                    // 替换end位置
                    replace(end, start);

                    // 结束里层循环
                    break;
                }
                // 找不到比pivot大的元素
                start++
            }
        }

        // start 必定等于 end
        // 该位置就是轴点的位置
        arr[end] = pivot;

        // 左边继续寻找轴点
        createPivot(s, end);

        // 右边继续寻找轴点
        createPivot(end + 1, e);

    }

    createPivot();
}

/**
 * 归并排序
 * @param arr 
 */
const ms = (arr: number[]) => {
    const len = arr.length;
    // 不需要排序
    if (len < 2) return;

    /**
     * 合并
     * @param s 
     * @param m 
     * @param e 
     */
    const merge = (s: number, m: number, e: number) => {
        // 1. 拷贝[s, m)的左边数组
        const leftArr = arr.slice(s, m);

        // 2. 确定 ai, li, le, ri, re
        let ai = s,
            li = 0,
            le = m - s,
            ri = m,
            re = e;

        /**
         * 比较元素大小
         * @param l 
         * @param r 
         */
        const compare = (l: number, r: number) => arr[l] - leftArr[r]



        // 3. 开始循环比较排序
        while (li < le && ri < re) {
            if (compare(ri, li) < 0) {
                // 右边 < 左边
                arr[ai] = arr[ri++]
            } else {
                // 右边 >= 左边
                arr[ai] = leftArr[li++]
            }
            ai++;
        }

        // 右边先结束 (左边先结束不用考虑)
        for (let i = li; i < le; i++) {
            // 左边数组依次拷贝到arr的ai位置
            arr[ai++] = leftArr[i] 
        }
    }

    /**
     * 拆分合并
     * @param s 
     * @param e 
     */
    const sort = (s = 0, e = len) => {
        // 长度小于2了, 不需要拆分了
        if (e - s < 2) return;
        const m = (s + e) >> 1;

        sort(s, m);
        sort(m, e)
        return merge(s, m, e)
    }
    return sort(0, len)

}



const arr = randomArr(0, 100, 90),
    arr2 = arr.slice(),
    arr3 = arr.slice();


// bs(arr);
// console.log(isSorted(arr))

// ss(arr2);
// console.log(isSorted(arr2))

// debugger
// hs(arr3);
// console.log(arr3);
// console.log(isSorted(arr3));

// debugger
// console.log(arr)
// qs(arr)
// console.log(arr)
// console.log(isSorted(arr));

// console.log(arr)
// ms(arr)
// console.log(arr)
// console.log(isSorted(arr));

// console.log(arr)
// cs(arr)
// console.log(arr)
// console.log(isSorted(arr));

// [].sort((a, b) => a - b)


// console.log(arr)
// qs(arr)
// console.log(arr)
// console.log(isSorted(arr));

console.log(arr)
ms(arr)
console.log(arr)
console.log(isSorted(arr));


/**
 * 简单实现Array.prototype.sort
 * @param fn 
 */
Array.prototype.mysort = function <T>(this: Array<T>, fn: (a: T, b: T) => number) {
    const arr = this;
    const len = arr.length;
    // 元素小于2, 没必要排序
    if (len < 2) arr;

    /**
     * 交换两个元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    // 遍历元素，传递给fn
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            const res = fn(arr[j], arr[j + 1])
            // 返回值大于0, 需要交换
            if (res > 0) {
                swap(j, j + 1)
            }
        }
    }
}
